#include <vector>
#include <iostream>
#include <algorithm>

// 注意:不可重复的三元组
// 暴力解法三层循环
// 应该要使用unorder map来去重，， 我没有实现
namespace S1 {
    class Solution {
    public:
    std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
        std::vector<std::vector<int>> res;
        for (int i = 0; i < nums.size(); i ++) {
            int n1 = nums[i];
            
            for(int j = i + 1; j < nums.size(); j++) {
                int n2 = nums[j];
                for (int x = j + 1; x < nums.size(); x++) {
                    int n3 = nums[x];
                    if ((n1 + n2 + n3) == 0) {
                        std::vector<int> ns {n1, n2, n3};
                        res.push_back(ns);
                    } 
                }
            }
        }
        return res;
    }
};
}

// 排序加双指针
// 双指针的核心是  “随着第一个元素的递增，第二个元素是递减的， 那么就可以使用双指针的方法“
/***
 * 掌握双指针的关键是识别问题的单调性和可分解性
 * 
 * 比喻:调解两个人吵架
 * 想像你在调解两个正在吵架的人（A和B),他们站的位置代表数值大小:
 *  A站在左边，B站在右边
 *  他们吵得越凶，数值（音量）相加就越大
 *  你的目标是让他们冷静下来，使数值和接近目标值
 * 
 * “单调性”
 *      你知道A向右移动会增大音量，B向左移动会减小音量
 *      
 * “可分解性”
 *      你可以先固定其中一个人，只调节另一个人     
 * 
 * 单调性：当一个指针移动时，问题的某个关键属性(如和，差，乘积等)会朝着一个确定的方向变化(单调递增或递减)
 * 识别单调性的关键问题:
 *    当一个指针移动时，结果会如何变化
 *    这种变化是确定的（总是增大或总是减小）
 *    如果是，就存在单调性、
 * 
 * 可分解性：复杂的问题可以分解为若干个相似的子问题，每个子问题可以用相同的方法解决
 */
namespace S2 {
    class Solution {
    public:
        std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
            std::sort(nums.begin(), nums.end());
            int size = nums.size();
            std::vector<std::vector<int>> res;

            for (int first = 0; first < size; ++ first) {
                if (first > 0 && nums[first] == nums[first - 1]) {
                    continue;
                }

                int third = size - 1; // 最右端
                int target = -nums[first]; // 取负数 

                for (int second = first + 1; second < size; ++ second) {
                    if (second > first + 1 && nums[second] == nums[second - 1]) {
                        continue;
                    }

                    while (second < third && nums[second] + nums[third] > target)
                    {
                        third --;
                    }

                    if (second == third) {
                        break;
                    }

                    if (nums[second] + nums[third] == target) {
                        res.push_back({nums[first], nums[second], nums[third]});
                    }
                    
                }
            }

            return res;
        }
    };
}

// 最接近的三数之和
namespace S3 {
    class Solution {
        public:
        int threeSumClosest(std::vector<int>&nums, int target) {
            std::sort(nums.begin(), nums.end());
            int size = nums.size();
            int best = 1e7;  // 1e7是科学计数法，表示 10 的 7 次方，即 10,000,000 这是一个足够大的初始值，确保任何实际的三数之和都会比它更接近目标值

            auto update = [&](int cur) {
                if (abs(cur - target) < abs(best - target)) {
                    best = cur;
                }
            };

            for(int i = 0; i < size; i++) {
                if (i > 0 && nums[i] == nums[i - 1]) { // 保证和上一次枚举的元素不相等
                    continue;
                }
                int j = i + 1, k = size - 1;
                while ( j < k) {
                    int sum = nums[i] + nums[j] + nums[k];
                    if (sum == target) {
                        return target;
                    }
                    //更新
                    update(sum);
                    // 如果和大于target 移动末尾对应的指针
                    if (sum > target) {
                        int k0 = k - 1; 
                        // 优化，， 移动到下一个不相等的元素
                        while (j < k0 && nums[k0] == nums[k])
                        {
                            --k0;
                        }
                        k = k0;
                    } else {
                        int j0 = j + 1;
                        while (j0 < k && nums[j0] == nums[j]) {
                            ++j0;
                        }
                        j = j0;
                    }
                }
            }
            return best;
        }
    };
}

int main() {
    std::vector<int> nums {-1,0,1,2,-1,-4};
    S2::Solution s1;
    auto res =  s1.threeSum(nums);

    for (auto& v : res) {
        std::cout << " ";
        for (auto n : v) {
            std::cout << n;
        }
        std::cout << std::endl;
    }
    // -4 -1, 1, 2    -4, -1 , 2 
    std::vector<int> nums1 {-1,2,1,-4};
    S3::Solution s3;
    int res3 = s3.threeSumClosest(nums1, 1);
    return 0;
}